//给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并
//返回其根节点。 
//
// 
//
// 示例 1: 
// 
// 
//输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
//输出: [3,9,20,null,null,15,7]
// 
//
// 示例 2: 
//
// 
//输入: preorder = [-1], inorder = [-1]
//输出: [-1]
// 
//
// 
//
// 提示: 
//
// 
// 1 <= preorder.length <= 3000 
// inorder.length == preorder.length 
// -3000 <= preorder[i], inorder[i] <= 3000 
// preorder 和 inorder 均 无重复 元素 
// inorder 均出现在 preorder 
// preorder 保证 为二叉树的前序遍历序列 
// inorder 保证 为二叉树的中序遍历序列 
// 
//
// Related Topics 树 数组 哈希表 分治 二叉树 👍 2049 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2023-08-22 03:08:42
 * @description 105.从前序与中序遍历序列构造二叉树
 */
public class ConstructBinaryTreeFromPreorderAndInorderTraversal{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new ConstructBinaryTreeFromPreorderAndInorderTraversal().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

  //Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
          this.left = left;
         this.right = right;
      }
  }

class Solution {

/*
递归，时间On 空间on
	对于任意一颗树而言，前序遍历的形式总是

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
	即根节点总是前序遍历中的第一个节点。

	而中序遍历的形式总是

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
*/


		 private Map<Integer,Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
		int n=preorder.length;
		//构造hash,通过节点值定位index
		map=new HashMap<Integer,Integer>();
		for (int i = 0; i < n; i++) {
			map.put(inorder[i],i);
		}
		return my(preorder,inorder,0,n-1,0,n-1);
    }
	private TreeNode my(int[] pre,int[] in,int pre_l,int pre_r,int in_l,int in_r){
		if(pre_l>pre_r){
			return null;
		}
		//先序遍历的第一个节点就是根节点
		int pre_root=pre_l;
		//从终须遍历中定位根节点（题目中，无重复元素）
		int in_root=map.get(pre[pre_root]);
		//建立根节点
		TreeNode root = new TreeNode(pre[pre_root]);
		//计算左子树节点
		int l_size=in_root-in_l;
		//构造左右子树，并连接到根节点，其中先序从左边界+1的l_size对应中序左边界到根节点-1的元素
		root.left=my(pre,in,pre_l+1,pre_l+l_size,in_l,in_root-1);
		//先序左边界+l_size+1到pre_r对应中序根节点+1到右边界
		root.right=my(pre,in,pre_l+l_size+1,pre_r,in_root+1,in_r);
		return root;
	}
	/*
	*我们用一个栈保存已经遍历过的节点，遍历前序遍历的数组，一直作为当前根节点的左子树，
	* 直到当前节点和中序遍历的数组的节点相等了，那么我们正序遍历中序遍历的数组，
	* 倒着遍历已经遍历过的根节点（用栈的 pop 实现），找到最后一次相等的位置，把它作为该节点的右子树。
    上边的分析就是迭代总体的思想，代码的话还有一些细节注意一下。
    * 用一个栈保存已经遍历的节点，用 curRoot 保存当前正在遍历的节点。
*/
	public TreeNode buildTree1(int[] preorder, int[] inorder) {
		if (preorder.length == 0) {
			return null;
		}
		//栈，保存待处理右子树的根节点
		Stack<TreeNode> roots = new Stack<TreeNode>();
		int pre = 0;
		int in = 0;
		//先序遍历第一个值作为根节点
		TreeNode curRoot = new TreeNode(preorder[pre]);
		//保存根节点
		TreeNode root = curRoot;
		// 根节点入栈
		roots.push(curRoot);
		pre++;
		//遍历前序遍历的数组
		while (pre < preorder.length) {
			//出现了当前节点的值和中序遍历数组的值相等，说明左子树已经遍历完了，寻找是谁的右子树
			if (curRoot.val == inorder[in]) {
				//每次进行出栈，实现倒着遍历
				while (!roots.isEmpty() && roots.peek().val == inorder[in]) {
					curRoot = roots.peek(); // 回溯到父节点
					roots.pop(); // 出栈
					in++;  // 中序指针后移
				}
				//设为当前的右孩子
				curRoot.right = new TreeNode(preorder[pre]);
				//更新 curRoot
				curRoot = curRoot.right;  // 切换到右子树
				roots.push(curRoot); // 新节点入栈
				pre++;
			} else {
				// 不相等说明还在根节点的左子树中，继续往左
				//否则的话就一直作为左子树
				curRoot.left = new TreeNode(preorder[pre]);
				curRoot = curRoot.left;
				roots.push(curRoot);
				pre++;
			}
		}
		return root;

	}
	public TreeNode buildTree2(int[] preorder, int[] inorder) {
		List<TreeNode> st=new ArrayList<>();
		TreeNode cur=new TreeNode(preorder[0]);
		TreeNode root=cur;
		st.add(cur);
		int pre=1;
		int in=0;
		while (pre<preorder.length){
			if(cur.val==inorder[in]){
				while (!st.isEmpty()&&st.get(st.size()-1).val==inorder[in]){
					cur=st.get(st.size()-1);
					st.remove(st.size()-1);
					in++;
				}
				cur.right=new TreeNode(preorder[pre]);
				cur=cur.right;
				st.add(cur);
				pre++;
			}else{
				cur.left=new TreeNode(preorder[pre]);
				cur=cur.left;
				st.add(cur);
				pre++;
			}
		}
		return root;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
